package org.bloomfilter;

import java.util.BitSet;

public class BloomFilter {
    private BitSet bitSet;
    private int m;
    private int k = 8;
    private Hash[] hashes;

    public BloomFilter(int n, double f) {
        // 通过 n 和 f 计算出需要的 bit 数组长度
        m = (int)Math.ceil(n * Math.log(f) / Math.log(1.0 / Math.pow(2.0, Math.log(2.0))));
        bitSet = new BitSet(m);

        hashes = new Hash[k];
        for (int i = 0; i < k; i++) {
            hashes[i] = new Hash(m, i + 1);
        }
    }

    public void add(String element) {
        for (Hash hash : hashes) {
            int hashValue = hash.hash(element);
            bitSet.set(hashValue, true);
        }
    }

    public boolean contains(String element) {
        for (Hash hash : hashes) {
            int hashValue = hash.hash(element);
            if (!bitSet.get(hashValue)) {
                return false;
            }
        }
        return true;
    }

    private static class Hash {
        private int m;
        private int seed;

        public Hash(int m, int seed) {
            this.m = m;
            this.seed = seed;
        }

        public int hash(String element) {
            int result = 0;
            for (int i = 0; i < element.length(); i++) {
                result = seed * result + element.charAt(i);
            }
            return (m - 1) & result;
        }
    }
}